package array;

/**
 * 给你一个字符串数组 words 。words 中每个元素都是一个包含 两个 小写英文字母的单词。
 * 请你从 words 中选择一些元素并按 任意顺序 连接它们，并得到一个 尽可能长的回文串 。每个元素 至多 只能使用一次。
 * 请你返回你能得到的最长回文串的 长度 。如果没办法得到任何一个回文串，请你返回 0 。
 * 回文串 指的是从前往后和从后往前读一样的字符串。
 * <p>
 * 示例 1：
 * 输入：words = ["lc","cl","gg"]
 * 输出：6
 * 解释：一个最长的回文串为 "lc" + "gg" + "cl" = "lcggcl" ，长度为 6 。
 * "clgglc" 是另一个可以得到的最长回文串。
 * <p>
 * 示例 2：
 * 输入：words = ["ab","ty","yt","lc","cl","ab"]
 * 输出：8
 * 解释：最长回文串是 "ty" + "lc" + "cl" + "yt" = "tylcclyt" ，长度为 8 。
 * "lcyttycl" 是另一个可以得到的最长回文串。
 * <p>
 * 示例 3：
 * 输入：words = ["cc","ll","xx"]
 * 输出：2
 * 解释：最长回文串是 "cc" ，长度为 2 。
 * "ll" 是另一个可以得到的最长回文串。"xx" 也是。
 *
 * @author Jisheng Huang
 * @version 20250525
 */
public class LongestPalindrome_2131 {
    /**
     * 2 letter words can be of 2 types:
     * <p>
     * Where both letters are same
     * Where both letters are different
     * Based on the above information:
     * <p>
     * If we are able to find the mirror of a word, ans += 4
     * The variable unpaired is used to store the number of unpaired words with both letters same.
     * Unpaired here means a word that has not found its mirror word.
     * At the end if unpaired same letter words are > 0, we can use one of them as the center of the palindromic string.
     *
     * @param words the given String array
     * @return the length of the longest palindrome can be formed from the given string array
     */
    public static int longestPalindrome(String[] words) {
        int[][] map = new int[26][26];
        int ans = 0;

        for (String w : words) {
            int a = w.charAt(0) - 'a';
            int b = w.charAt(1) - 'a';

            if (map[b][a] > 0) {
                ans += 4;
                --map[b][a];
            } else {
                ++map[a][b];
            }
        }

        for (int i = 0; i < 26; ++i) {
            if (map[i][i] > 0) {
                ans += 2;
                break;
            }
        }

        return ans;
    }

    public static void main(String[] args) {
        String[] words = {"lc", "cl", "gg"};
        System.out.println(longestPalindrome(words));

        words = new String[]{"ab", "ty", "yt", "lc", "cl", "ab"};
        System.out.println(longestPalindrome(words));

        words = new String[]{"cc", "ll", "xx"};
        System.out.println(longestPalindrome(words));
    }
}
